package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/6/28 12:50
 * @Version 1.0
 **/
public class ReverseLinkedList {
    // TODO 方法一：使用头插法，遍历链表将节点一个一个插入结果链表中
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode result = head, pre, now = head.next;
        result.next = null;
        while (now != null) {
            pre = now;
            now = now.next;
            pre.next = result;
            result = pre;
        }
        return result;
    }

    // TODO 方法二：直接将原来的链表的next指针反转
    public ListNode reverseList2(ListNode head) {
        dfs(head);
        return result;
    }

    boolean flag = true;
    ListNode result;
    public ListNode dfs(ListNode head) {
        if (head == null || head.next == null) {
            if (flag) {
                result = head;
                flag = false;
            }
            return head;
        }
        ListNode temp = dfs(head.next);
        temp.next = head;
        head.next = null;
        return head;
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
